package A_review.review9_13;

import listNodePractice.ListNode;

import java.util.Optional;
import java.util.PriorityQueue;

public class MergeKListNodes {


    public ListNode mergeKLists(ListNode[] lists) {
        if (lists.length==0){
            return  null;
        }
        PriorityQueue<ListNode> priorityQueue= new PriorityQueue<>(lists.length);

        for (ListNode head : lists) {
            if (head!=null){
                priorityQueue.add(head);
            }
        }

        ListNode dumpy = new ListNode(-1);
        ListNode p=dumpy;
        while (!priorityQueue.isEmpty()){
            ListNode node = priorityQueue.poll();
        p.next=node;
        if (node.next!=null){
            priorityQueue.add(node.next);
        }
        p=p.next;

        }
        return  dumpy.next;
    }


    public ListNode mergeKLists1(ListNode[] lists) {
        if (lists.length == 0) return null;
        ListNode dumpy = new ListNode(-1);
        ListNode q=dumpy;
        PriorityQueue<ListNode> pq = new PriorityQueue<>(
                lists.length, (a, b)->(a.val - b.val));
        for (ListNode p:lists) {
//            todo:缺少了这个判断条件
            if (p!=null){
                pq.add(p);
            }
        }
        while (!pq.isEmpty()){
            ListNode poll = pq.poll();
            q.next=poll;

            if (poll.next!=null){
                pq.add(poll.next);
            }
            q=q.next;
        }
        return  dumpy.next;
// if (lists.length == 0) return null;
//     // 虚拟头结点
//     ListNode dummy = new ListNode(-1);
//     ListNode p = dummy;
//     // 优先级队列，最小堆
//     PriorityQueue<ListNode> pq = new PriorityQueue<>(
//         lists.length, (a, b)->(a.val - b.val));
//     // 将 k 个链表的头结点加入最小堆
//     for (ListNode head : lists) {
//         if (head != null)
//             pq.add(head);
//     }

//     while (!pq.isEmpty()) {
//         // 获取最小节点，接到结果链表中
//         ListNode node = pq.poll();
//         p.next = node;
//         if (node.next != null) {
//             pq.add(node.next);
//         }
//         // p 指针不断前进
//         p = p.next;
//     }
//     return dummy.next;
    }



}
